package com.gxc.array;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 求最大子矩阵的大小
 * 给定一个整型矩阵 map，其中的值只有 0 和 1 两种，
 * 求其中全是 1 的所有矩形区域中，最大的矩形区域里 1 的数量。
 */
public class MaxRecSize {

    public static void main(String[] args) {
        int[][] map = {
                {1,0,1,1,},
                {1,1,1,1},
                {1,1,1,0}
        };
        System.out.println(handle(map));
        System.out.println(maxRecFromBottom(new int[]{1,0,1,1,}));
        System.out.println(maxRecFromBottom(new int[]{2,1,3,3,}));
    }

    private static int handle(int[][] map) {
        if (map.length == 0 || map[0].length == 0) return 0;
        
        //当前行作为底，有多少个连续的1
        int[] height = new int[map[0].length];
        int max = 0;
        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map[i].length; j++) {
                if (map[i][j] == 1) {
                    height[j] = height[j]+1;
                } else {
                    height[j] = 0;
                }
            }
            //计算当前行作为底时，最大的数量
            max = Math.max(max, maxRecFromBottom(height));
        }
        return max;
    }

    //给定一个可能含重复值的数组arr，找到每个i位置左边和右边距离i最近的且值比i小的位置(没有返回-1)，
    public static int maxRecFromBottom(int[] height) {
        if (height == null || height.length == 0) return 0;
        int max = Integer.MIN_VALUE;
        Stack<List<Integer>> stack = new Stack<>();
        int[][] near = new int[height.length][2];
        for (int i = 0; i < height.length; i++) {
            while (!stack.isEmpty() && height[i] < height[stack.peek().get(0)]) {
                List<Integer> pop = stack.pop();
                int min = stack.isEmpty()?-1:stack.peek().get(stack.peek().size()-1);
                for (int j = 0; j < pop.size(); j++) {
                    max = Math.max((i-min -1)* height[pop.get(j)], max) ;
                    near[pop.get(j)][0] = min;
                    near[pop.get(j)][1] = i;
                }
            }
            if (!stack.isEmpty() && height[i] == height[stack.peek().get(0)]) {
                stack.peek().add(i);
            } else {
                List<Integer> list = new ArrayList<>();
                list.add(i);
                stack.push(list);
            }
        }
        while (!stack.isEmpty()) {
            List<Integer> pop = stack.pop();
            int min = stack.isEmpty()?-1:stack.peek().get(stack.peek().size()-1);
            for (int j = 0; j < pop.size(); j++) {
                max = Math.max((height.length-min -1)* height[pop.get(j)], max) ;
                near[pop.get(j)][0] = min;
                near[pop.get(j)][1] = -1;
            }
        }
        return max;
    }
}
